Computer programs vary in scope and usage. They range from web browsers and word processors to video games and business applications. While the functionality of computer programs may vary greatly, all programs commonly include a series of instructions that direct a computer(s) to perform a task(s).
One common technique for structuring a program is to break the program into multiple subroutines or functions. Functions typically operate to accomplish a specific task. For example, a sales function may execute instructions to place a new sales order. As part of this process, the sales function may call a tax function that calculates the sales tax for the new sales order. FIG. 1A illustrates an example of multiple function calls. Main 22 calls SalesOrder 24 which then calls SalesOrder 26 again. Subsequently, Tax 28 is called, which then returns to SalesOrder 26.
The computer stores its instructions in memory. The instructions to carry out functions are typically located in different memory locations of a computer. During program execution, the computer needs to know how to transfer the execution (e.g., the currently executing instruction) from one function to another and sometimes back again. To use the above sales and tax example, this may be thought of as moving a task from the sales department to the accounting (or tax) department in a company and back again.
To transfer execution from the sales function to the tax function above (e.g., SalesOrder 26 to Tax 28), the relative or absolute location of the tax function can inserted into the sales function. This works fine to get from the sales function to the tax function. However, a way must also be provided to get back. Because multiple functions may call the tax function, the tax function may not always return to the same calling function. Therefore, when tax 28 returns from executing and the processor needs to transfer execution back to sales 26, it may not be possible to rely on an insertion of location. For example, it would be like assuming that just because one flight from Seattle landed at Washington-Dulles airport that all passengers from all flights who landed at Washington-Dulles wish to return to Seattle. Rather, the computer must keep track of which function called the currently executing function so that control can be returned to the correct place when the currently executing function finishes. This issue may be further complicated by “nesting”, e.g., a first function calling a second function, which calls a third function, etc.
Certain computer architectures use a stack to store executing functions in memory. To address the above discussed execution issues, a stack includes call stack information that helps determine the sequence of how the functions are called. Thus, a call stack can be thought of as a breadcrumb trail that allows an executing program to “find” its way back after a function (e.g., the tax function above) finishes executing. FIG. 1B illustrates the use of a stack for the above function calls in FIG. 1A. Here, each time a function is called, the function is “pushed” to the stack as a stack frame. These stack frames serve, in part, to store the “breadcrumb,” or call stack, for executing the program. Correspondingly, when a function is finished executing, it is “popped” from the stack and program control returns to the caller function by referencing the stored “breadcrumb.” For example, the second time the SalesOrder function is called, a second stack frame associated with SalesOrder is added to the stack on top of the currently existing stack frame. A part of this new stack frame is the address, or breadcrumb that allows the program to return to the first SalesOrder when the second SalesOrder is complete. Thus, a call stack may organize program execution so that execution may be passed back and forth between functions in an orderly way.
Information in call stacks can also help analyze the flow of a computer program. Understanding the current execution context of a function (e.g., did the function Main call SalesOrder or did SalesOrder call SalesOrder?) can help resolve bugs, performance problems, or other issues. In contrast, simply looking at the current function that is executing may not provide enough information for a developer to properly asses the status of the computer program. For example, is the problem with the current function or the function that called the current function?
The example code section in Table 1 and the corresponding call stacks in FIG. 7 may illustrate this concept:
TABLE 1Line #Instruction 1Main( ) { 2SalesOrder(newComputer); 3CalculateTax(“100”); 4Return;} 5Function SalesOrder (var order) { 6If order == newComputer { 7SalesOrder(mouse); } 8CalculateTax(order); 9Return;}10Function CalculateTax (var order) {11var salesTax = .05;12Print(order.price * salesTax);13Return;}
In this example, the function “CalculateTax(var order)” is called twice (Line 3 and Line 8). In this instance, the two function calls have two different breadcrumb trails (e.g., call stacks). Further, in both cases, the nature of the breadcrumb trail can help provide information on the nature of the program flow.
For example, call stack 602 includes two stack frames, each of which includes a return address (e.g., breadcrumb). Stack frame 606A relates to the execution of the CalculateTax function and has a return address of 8. Similarly, stack frame 608 is associated with the execution of the SalesOrder function and will return to line 2. Conversely, while the same CalculateTax function may be executing in relation to stack 604 and associated with stack frame 606B, the context of the execution may be different from that in stack 602.
In addition to storing the return address, a stack frame may also store other types of information. For example, a stack frame may include locale variables or parameters that may only exist for that instance of the function.
For those writing and developing computer programs, such information regarding how a given program executes (or flows) can be valuable in developing better, more efficient software and resolving problems. Thus, it would be beneficial to provide call stack information so that a program's flow may be determined.
The way to get call stack information may vary depending on the type of computer architecture a program is executing on. In certain types of computer architectures, a portion of a stack may be stored on the processor rather than in memory. For example, an ARM processor may store the return address of the currently executing function in the link register (e.g., the R14 register). However, it may not be straightforward to determine what the whole call stack looks like (e.g., as shown in FIG. 1B). To compound the problem of determining the call stack, it may be desirable to decrease the amount of time and/or memory used to determine what the call stack looks like.
One area of computing that this may be the case is in the area of handheld devices where the small size, cost considerations, and power constraints for the operating processors all may factor into the architecture. Furthermore, in mobile computing, using debug versions of software code may be prohibitive because of the processing limitations of the handheld device. Also, the addition of debug information to certain programs may have a dramatic effect on performance. For example, some applications for handheld devices may be particularly processing intensive (e.g., more so than a word processing application). Thus, adding debug code may not be a realistic solution for an engineer attempting to diagnose a performance problem (or some other issue) for a given application that operates on a handheld device.
Accordingly, it would be desirable to develop systems and/or methods that determine or assist in discovering call stacks that relate to an executing computer program.
In certain example embodiments, as part of obtaining raw stack information, the current program counter of an executing program is stored. This may indicate what instruction the program is currently executing. At this point the current depth of the stack is also stored to the raw stack information. In certain example embodiments, this information may be associated with the currently executing instruction that is/was stored. The depth may be determined by subtracting the starting address of the stack from the address pointed to by the stack pointer. After these values, the current return address for the currently executing function may be stored. In certain example embodiments, if the address is a valid address (e.g., within the address range determined previously) the information may be located in the link register. This address may be stored with an associated depth value, for example, −1 to indicate that the address was stored in the link register.
After storing the above values, the process walks down the address space of the call stack (e.g., between the stack pointer and the starting address of the stack) storing addresses that are classified as “valid” (based on the above determined range) with an associated depth (e.g., subtract the current depth of the current address from the starting point address of the call stack). The process continues until the current depth is equal to the starting depth.
In certain example embodiments, addresses in the raw stack data may be mapped to associated function names. In certain example embodiments, this may be done by examining the symbol file and comparing the addresses in the raw stack with the addresses in the symbol or compile file. In addition, for the functions in the raw stack data, the executable assembly code for those functions may be obtained. In certain example embodiments, these techniques may be performed on a host computing system.
In certain example embodiments, a process may loop through the returned raw stack information and piece together related (e.g., parent-child or caller/callee relationships) to form a call stack.
Thus, for example:                1) If the end of the stack has been reached, stop looping;        2) Determine the depth of the stack of the current address in the stack;        3) If the depth is zero, and the process is not at the bottom of the stack, the Link Register may have the parent function. This may be the next item on the raw stack.        4) Otherwise, if there has not been an error in finding the parent, use the current stack depth to find the next function in the stack.                    a. If the link register was not stored on the stack, the link register may have the parent function (e.g., as the next item on the stack).            b. Add the current depth to the known stack depth (e.g., the information of the raw stack information) to determine where the next function is stored on the stack. If the process locates an address at the calculated depth, then that address may be the parent function.                        5) If the process has not yet found a function it may determine all possible stack depths for a function, and try each of them, from the largest depth to the smallest depth, to see if a function can be found.                    a. In this instance, values that may traverse the stack in the wrong direction may be ignored.                        6) If the process only locates the program counter and the link register and an error is not yet set, set an error and reset the current depth to the initial stack depth and begin again at 1).        7) If the process still has not found anything, a place holder may be set (e.g., “unknown”) to let the user know of the problem.        
In certain example embodiments, no debugging information may be used. For example, certain example embodiments may operate such that no DWARF debug information is included in the computer program.
In certain example embodiments, it may be desirable to relatively decrease the processing and memory impact on a computer running a computer program while obtaining call stack information. In certain example embodiments, an executing computer program may be relatively unaffected by a process or program that is run to at least help discover or build a call stack.